package java学习.算法.动态规划.暴力递归与动态规划;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/5/16 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 字符串子序列问题 {
//    子序列： 可以不连续，但需要保持原顺序
//    子串： 连续且保持原顺序

//    1.打印一个字符串的全部子序列
//     1. str：原字符串数组
//     2。 index 当前走到的下标
//     3. 返回集合
//     4。 生成的路径，之后加入集合ans
    public static void main(String[] args) {
        System.out.println(getAllSubsForString("abc"));

    }
    public static List<String> getAllSubsForString(String str){
        List<String> ans = new ArrayList<>();
        char[] chars = str.toCharArray();
        String path = "";
        process1(chars,0,ans,path);
        return ans;
    }

    public static void process1(char[] str, int index, List<String> ans, String path) {

        // 如果 index到最后了，就将此时的 path加入list：
        if (index==str.length){
            ans.add(path);
            return;
        }
        String no = path; // 没加入后面的字符串：
        process1(str,index+1,ans,no);
//        加入了后面的字符串：
        String yes = path+ String.valueOf(str[index]);
        process1(str,index+1,ans,yes);


    }

//2、打印一个字符串的全部子序列，要求不要出现重复字面值的子序列 HashSet
    public static void process2(char[] str, int index, HashSet<String> ans, String path) {

        // 如果 index到最后了，就将此时的 path加入list：
        if (index==str.length){
            ans.add(path);
            return;
        }
        String no = path; // 没加入后面的字符串：
        process2(str,index+1,ans,no);
//        加入了后面的字符串：
        String yes = path+ String.valueOf(str[index]);
        process2(str,index+1,ans,yes);


    }

}
